1. Field of the Invention
The present invention pertains generally to telecommunications, and particularly to the compression of headers of packets such as media packets.
2. Related Art and Other Considerations
Due to the tremendous success of the Internet, it has become a challenging task to make use of the Internet Protocol (IP) over all kinds of links. However, because of the fact that the headers of the IP protocols are rather large, it is not always a simple task to make this come true for narrowband links, such as cellular links, for example. As an example, consider ordinary speech data transported by the protocols (IP, UDP, RTP) used for Voice-over-IP (VoIP), where the header may represent about 70% of the packet resulting in a very inefficient usage of the link.
The term “header compression” (HC) encompasses the art of minimizing the necessary bandwidth for information carried in headers on a per-hop basis over point-to-point links. Header compression techniques in general have a more than ten-year-old history within the Internet community. Several commonly used header compression protocols exist, such as the following: (1) Van Jacobson. Compressing TCP/IP Headers for Low-Speed Serial Links. IETF RFC 1144, IETF Network Working Group, February 1990; (2) Mikael Degermark, Björn Nordgren, Stephen Pink. IP Header Compression, IETF RFC 2507, IETF Network Working Group, February 1999; and (3) Steven Casner, Van Jacobson. Compressing IP/UDP/RTP Headers for Low-Speed Serial Links, IETF RFC 2508, IETF Network Working Group, February 1999, all of which are incorporated by reference herein in their entirety.
Header compression takes advantage of the fact that some fields in the headers are not changing within a flow, or change with small and/or predictable values. Header compression schemes make use of these characteristics and send static information only initially, while changing fields are sent with their absolute values or as differences from packet to packet. Completely random information has to be sent without any compression at all.
Header compression is thus an important component to make IP services over wireless, such as voice and video services, economically feasible. Header compression solutions have been developed by the Robust Header Compression (ROHC) Working Group of the Internet Engineering Task Force (IETF) to improve the efficiency of such services.
Robust Header Compression (ROHC), as defined in RFC 3095 (Bormann, C., “RObust Header Compression (ROHC): Framework and four profiles: RTP, UDP, ESP, and uncompressed”, RFC 3095, Internet Engineering Task Force, July 2001), is an extensible framework for which profiles for compression of various protocols may be defined. For real-time multimedia services (e.g. voice, video), the application data is transported end-to-end within an IP/UDP/RTP stream. Header compression of IP/UDP/RTP is defined by the ROHC profile 0x0001 (ROHC RTP) and is applicable for Voice-over-IP (VoIP) services among others. The ROHC RTP header compression scheme has been designed to efficiently compress the IP/UDP/RTP headers over an arbitrary link layer.
A number of other ROHC profiles have also been defined for compression. Among these are (1) IP/UDP/RTP headers (described in: Jonsson, L. and G. Pelletier, RObust Header Compression (ROHC): A Link-Layer Assisted ROHC Profile for IP/UDP/RTP, IETF RFC 3242, April 2002; and Liu, Z and K. Le, Zero-byte Support for Bidirectional Reliable Mode (R-mode) in Extended Link-Layer Assisted RObust Header Compression (ROHC) Profile, IETF RFC 3408, December 2002); (2) IP only headers (described in: Jonsson, L. and G. Pelletier, RObust Header Compression (ROHC): A compression profile for IP, IETF RFC 3843, June 2004); (3) IP/TCP headers (described in: Pelletier, G., Jonsson, L., West, M. and R. Price RObust Header Compression (ROHC): TCP/IP Profile (ROHC-TCP), Internet Draft (work in progress), <draft-ietf-rohc-tcp-08.txt>, October 2004); and (4) IP/UDP-Lite/RTP headers (described in: Pelletier, G., RObust Header Compression (ROHC): Profiles for UDP-Lite, Internet Draft (work in progress), <draft-ietf-rohc-udp-lite-04.txt>, June 2004). All RFCs cited herein are incorporated by reference herein in their entireties.
Except for negotiation (see also Bormann, C., Robust Header Compression (ROHC) over PPP, IETF RFC 3241, April 2002), ROHC profiles only requires framing and error detection to be provided by the link layer, while all other functionality is handled by the ROHC scheme itself.
The ROHC profiles defined in RFC 3095, RFC 3242, RFC 3408, “IP-ONLY” (Jonsson, L. and G. Pelletier, RObust Header Compression (ROHC): A compression profile for IP, IETF RFC 3843, June 2004) and “ROHC-UDPLite” (Pelletier, G., RObust Header Compression (ROHC): Profiles for UDP-Lite, Internet Draft (work in progress), <draft-ietf-rohc-udp-lite-04.txt>, June 2004) all support three different modes of operation. In short, for a specific context, the mode of operation controls the actions and the logic to perform as well as the packet types to use during different states of the header compression operation. Packet types and formats that are allowed may vary from one mode to the other. The Unidirectional mode (U-mode) is used at the beginning of any ROHC compression before any transition to other modes may occur. The Bidirectional Optimistic mode (O-mode) seeks to maximize the compression efficiency and sparse usage of the feedback channel. The Bidirectional Reliable mode (R-mode) seeks to maximize robustness against loss propagation and context damage propagation.
When in U-mode, packets are sent from compressor to decompressor only. The U-mode is thus usable over links where a return path from decompressor to compressor is either not desired or not available. Periodical refreshes are used in U-mode. The U-mode is particularly applicable to broadcast or multicast channels.
The O-mode is similar to the U-mode with the difference that a feedback channel is used to send error recovery requests and (optionally) acknowledgements of significant context updates from the decompressor to compressor. For most ROHC profiles, the U-mode and the O-mode are often indistinctly referred to using the term U/O-mode, due their rather similar characteristics—such as an identical set of packets formats for both modes.
The R-mode differs significantly from the two other modes, mainly by making a more extensive usage of the feedback channel and a stricter logic for performing context updates. The R-mode also uses a few different packet types only understood and useful in this mode.
Each mode of operation has different properties in terms of compression efficiency, robustness and processing complexity. Mode transitions may only be initiated by the decompressor. ROHC does not specify how and when each mode should be used (other than that ROHC compression must always start in U-mode). Therefore, the logic for mode transitions is an implementation decision and may be based on measurements of the link characteristics, link conditions, implementation optimizations for a specific mode or may be based on other algorithms. In particular, for Broadcast/Multicast type of services, header compression operates in the unidirectional mode (U-Mode) only, as normally for such services a feedback channel from decompressor to compressor is not available or desired.
A header compression scheme (such as a ROHC Profile) can be conceptualized and/or realized as a state machine. A challenging task is to keep the compressor and decompressor states, called contexts, consistent with each other, while keeping the header overhead as low as possible. There is one state machine for the compressor, and one state machine for the decompressor. The compressor state machine directly impacts the level of compression efficiency, as it is an important part of the logic controlling the choice of compressed packet type to be sent. The purpose of the decompressor state machine is mainly to provide the logic for feedback (if applicable) and to identify the packet types for which decompression may be attempted.
A compression context contains and maintains relevant information about past packets, and this information is used to compress and decompress subsequent packets. As explained in the ROHC documentation, the context of the compressor is the state it uses to compress a header. The context of the decompressor is the state it uses to decompress a header. Either of these or the two in combination are usually referred to as “context”, when it is clear which is intended. The context contains relevant information from previous headers in the packet stream, such as static fields and possible reference values for compression and decompression. Moreover, additional information describing the packet stream is also part of the context, for example information about how the IP Identifier field changes and the typical inter-packet increase in sequence numbers or timestamps.
For the ROHC profiles defined in RFC 3095, RFC 3242, RFC 3408, “IP-ONLY” (Jonsson, L. and G. Pelletier, RObust Header Compression (ROHC): A compression profile for IP, IETF RFC 3843, June 2004) and “ROHC-UDPLite” (Pelletier, G., RObust Header Compression (ROHC): Profiles for UDP-Lite, Internet Draft (work in progress), <draft-ietf-rohc-udp-lite-04.txt>, June 2004), FIG. 1 shows the compressor state machine. For ROHC compression, the three compressor states are the Initialization and Refresh (IR), First Order (FO), and Second Order (SO) states. The compressor starts in the lowest compression state (IR) and transits gradually to higher compression states. The compressor will always operate in the highest possible compression state, under the constraint that the compressor is sufficiently confident that the decompressor has the information necessary to decompress a header compressed according to that state. See, e.g., RFC 3095, section 4.3.1 (Carsten Bormann, et al. RObust Header Compression (ROHC): Framework and four profiles: RTP, UDP, ESP and uncompressed; IETF RFC 3095, April 2001). In particular while operating in U-Mode, decisions about transitions between the various compression states are normally taken by the compressor on the basis of variations in packet headers and periodic timeouts.
According to RFC 3095 defines the Initialization and Refresh (IR) State, in section 4.3.1, the purpose of the IR state is to initialize the static parts of the context at the decompressor or to recover after failure. In this state, the compressor sends complete header information. This includes all static and nonstatic fields in uncompressed form plus some additional information. The compressor stays in the IR state until it is fairly confident that the decompressor has received the static information correctly.
The IR state is thus the state were the compression level is the lowest. FIG. 2, taken from RFC 3095, section 5.3.1, describes the U-Mode state machine. In the U-mode state machine of FIG. 2, Timeout_1 typically corresponds to a periodic sending of the static (and possibly also dynamic) parameters of the decompressor context, while Timeout_2 typically corresponds to a periodic sending of only the dynamic parameters of the decompressor context.
In addition, the context replication (CR) mechanism for ROHC profiles introduce an additional state, the CR state. See, Pelletier, G., Robust Header Compression (ROHC): Context replication for ROHC profiles, Internet Draft (work in progress), <draft-ietf-rohc-context-replication-01.txt>, October 2003. To date, only the [ROHC-TCP] profile specifies support for context replication, but other profiles may also support it provided their corresponding standard is updated. The CR state may also be used by a profile operating in U-Mode. FIG. 3 shows the logic added to the previous state machine for the CR state. In U-Mode, downward transitions are performed according to the same logic as described above.
FIG. 4, taken from RFC 3095, section 5.3.2, illustrates an example U-Mode decompressor state machine. The state of the decompressor dictates what type of compressed packet may be decompressed. In the No Context (NC) state, only packets initializing the static part may be decompressed (e.g. ROHC IR packets). In the Static Context (SC) state, only packets containing sufficient information on the dynamic parameters (e.g. ROHC IR-DYN or UOR-2 packets) may be decompressed. In the Full Context (FC) state, any packet may be decompressed. Thus, depending on the condition of the channel and on the success rate of the decompression, the decompressor state machine will transit between the different states and will have to wait for the reception of a suitable packet for attempting decompression.
In unidirectional operation, there is no feedback sent back to the compressor. Therefore, in unidirection operation, the decompressor may (in the worst cases) have up to Timeout_1 of waiting time without possibility to start decompression of the received packets, and up to Timeout_2 before it can re-start compression after severe context damage to the dynamic information.
To date, header compression algorithms have been designed under the assumption that packets (whose headers are compressed) are delivered essentially in order, and thus that the packets do not require substantial re-ordering upon receipt. In accordance with such assumption, most conventional header compression algorithms operate on the premise that reordering of a header-compressed packet between a compressor and a decompressor is not possible. See, e.g., Van Jacobson, Compressing TCP/IP Headers for Low-Speed Serial Links, IETF RFC 1144, IETF Network Working Group, February 1990; Mikael Degermark, Björn Nordgren, Stephen Pink, IP Header Compression, IETF RFC 2507, IETF Network Working Group, February 1999; Steven Casner, Van Jacobson, Compressing IP/UDP/RTP Headers for Low-Speed Serial Links, IETF RFC 2508, IETF Network Working Group, February 1999; and Carsten Bormann, et al. RObust Header Compression (ROHC): Framework and four profiles: RTP, UDP, ESP and uncompressed, IETF RFC 3095, April 2001, all of which are incorporated herein by reference.
A few header compression algorithms allow or accommodate only slight out-of-sequence delivery of packets, and thus only slight reordering of packets upon reception (with a depth of very few packets). See, e.g., Koren, T., Casner, S., Geevarghese, J., Thompson B. and P. Ruddy, Enhanced Compressed RTP (CRTP) for Links with High Delay, Packet Loss and Reordering, IETF RFC 3545, IETF Network Working Group, July 2003; and Pelletier, G., Jonsson, L. and Sandlund, K., Robust Header Compression (ROHC) over Channels that can reorder packets, Internet Draft (work in progress), <draft-pelletier-rohc-over-reordering-00.txt>, June 2004, incorporated herein by reference.
The design of compression algorithms has primarily focused on improving the tolerance against packet losses, driven by the properties of wireless cellular links. Encoding of sequential information has been improved from cumulative delta encoding to more robust Window Least Significant Bit (W-LSB) encoding. Cumulative delta coding is described, e.g., in Van Jacobson, Compressing TCP/IP Headers for Low-Speed Serial Links, IETF RFC 1144, IETF Network Working Group, February 1990; Mikael Degermark, Björn Nordgren, Stephen Pink. IP Header Compression, IETF RFC 2507, IETF Network Working Group, February 1999; and, Steven Casner, Van Jacobson. Compressing IP/UDP/RTP Headers for Low-Speed Serial Links, IETF RFC 2508, IETF Network Working Group, February 1999. Window Least Significant Bit (W-LSB) encoding is described in Carsten Bormann, et al. RObust Header Compression (ROHC): Framework and four profiles: RTP, UDP, ESP and uncompressed, IETF RFC 3095, April 2001. Other approaches have also been used, such as reducing the compression ratio for sequential information (Koren, T., Casner, S., Geevarghese, J., Thompson B. and P. Ruddy, Enhanced Compressed RTP (CRTP) for Links with High Delay, Packet Loss and Reordering, IETF RFC 3545, IETF Network Working Group, July 2003) or tweaking some parameters of existing encoding methods (Pelletier, G., Jonsson, L. and Sandlund, K., Robust Header Compression (ROHC) over Channels that can reorder packets, Internet Draft (work in progress), <draft-pelletier-rohc-over-reordering-00.txt>, June 2004).
Consistently with the foregoing observations, the IETF ROHC working group (WG) has designed header compression algorithms (profiles) with the assumption that the channel between the compressor and the decompressor will not reorder the header-compressed packets. As such, the channel is required to maintain packet ordering for each compressed flow. Encoding methods have been defined with this assumption in order to aggressively compress headers and achieve a high compression ratio. For some profiles, modifications can be made to the logic and/or to some encoding methods (e.g. LSB) in order to handle a very small (less than 5 packets) amount of reordering (Pelletier, G., Jonsson, L. and Sandlund, K., Robust Header Compression (ROHC) over Channels that can reorder packets, Internet Draft (work in progress), <draft-pelletier-rohc-over-reordering-00.txt>, June 2004)). However, changes to fields that are not encoded using sequential information (e.g. semi-static fields) limit the possibility to decompress a reordered packet and/or to prevent severe context damage in the presence of moderate (tens of packets) or high (hundreds of packets) reordering.
With the upcoming development of wireless links with higher bit rates and lower latencies (still relatively high latency with respect to the bit rate), the in-order delivery assumption will likely no longer be operative. There will be a need for header compression/decompression algorithms which not only are robust not against packet losses, but also against out-of-order delivery and thus reordering of packets.
What is needed, therefore, and an object of the present invention, are method and apparatus capable of header decompression even for out-of-sequence packets.